home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.02 Feb 96 / 12.02 Challenge / find.c < prev   
Encoding:
C/C++ Source or Header  |  1995-12-11  |  20.5 KB  |  786 lines  |  [TEXT/R*ch]
  1. /* Copyright © 1995 Gustav Larsson */
  2.  
  3. /* ------------------------------------------------------ */
  4. /*                  Constants & Types                     */
  5.  
  6. #define ALPHABET_SIZE 256
  7.  
  8. #define ALLOC_SIZE(n) ((n+3) & -4L) /* next multiple of 4 */
  9.  
  10. #define HASH_BUCKETS 1024           /* must be power of 2 */
  11. #define HASH_MASK (HASH_BUCKETS - 1)
  12.  
  13. #define NO_NULL_CHAR 'A'
  14.  
  15. #define NULL 0
  16. //#define TRUE 1
  17. //#define FALSE 0
  18.  
  19. typedef unsigned char  uchar;
  20. typedef unsigned short ushort;
  21. typedef unsigned long  ulong;
  22.  
  23. typedef struct Word Word;
  24. typedef struct Occurrence Occurrence;
  25. typedef struct Private Private;
  26.  
  27. /*
  28.   A block of occurrence positions. We pack in as many
  29.   occurrences as possible into a single block, from 3 to 6
  30.   depending on textLength.
  31.  
  32.   The first entry in the block is always used. The
  33.   remaining entries are in use if they are not zero.
  34.   These facts are used several places to simplify the code.
  35. */
  36.  
  37. struct Occurrence {
  38.   Occurrence *next;
  39.   union {
  40.     ushort pos2[6];   /* 2 bytes/occurrence */
  41.     struct {
  42.       ushort lo[4];
  43.       uchar  hi[4];
  44.     } pos3;           /* 3 bytes/occurrence */
  45.     long pos4[3];     /* 4 bytes/occurrence */
  46.   } p;
  47. };
  48.  
  49. /*
  50.   There is one Word struct for each distince word.
  51.   The word's length is stored in the top eight bits
  52.   of the hash value. There's no need to store the
  53.   characters in the word since we can just look at
  54.   the first occurrence (first entry in Word.first).
  55. */
  56.  
  57. struct Word {
  58.   Word        *next;
  59.   ulong       hash;
  60.   Occurrence  *last;
  61.   Occurrence  first;
  62. };
  63.  
  64. /*
  65.   The structure of our private storage. The hashCodes[]
  66.   array serves two purposes: it distinguishes alphanumeric
  67.   from non-alphanumeric characters, and it provides a
  68.   non-zero hash code for each alphanumeric character.
  69.   The endParsedText field will be -1 if there was enough
  70.   private memory to parse all the text. Otherwise, it points
  71.   to the start of the unparsed text. nullChar is used by
  72.   the BMH_Search() function when we must search unparsed
  73.   text for an occurrence.
  74. */
  75.  
  76. struct Private {
  77.   ulong hashCodes [ ALPHABET_SIZE ];
  78.   Word  *hashTable [ HASH_BUCKETS ];
  79.   long  endParsedText;  /* start of parsed text           */
  80.   long  posBytes;       /* POS_x_BYTES, below             */
  81.   char  nullChar;       /* char not appearing in the text */
  82.   long  heap;           /* start of private heap          */
  83. };
  84.  
  85. /* ------------------------------------------------------ */
  86. /*                        Macros                          */
  87.  
  88. /*
  89.   These macros simplify access to the occurrence positions
  90.   stored in an Occurrence struct. Posbytes is a macro
  91.   argument that is usually set to private->posBytes.
  92.   However, you can also use a constant for posbytes, which
  93.   lets the compiler choose the right case at compile time,
  94.   producing smaller and faster code.
  95. */
  96.  
  97. #define POS_2_BYTES 1   /* word position fits in 2 bytes */
  98. #define POS_3_BYTES 0   /* fits in 3 bytes; usual case   */
  99. #define POS_4_BYTES 2   /* fits in 4 bytes               */
  100.  
  101. #define GET_POS(pos,occur,index,posbytes)           \
  102.   {                                                 \
  103.     if ( (posbytes) == POS_3_BYTES )                \
  104.       pos = ((long)(occur)->p.pos3.hi[index] << 16) \
  105.           + (occur)->p.pos3.lo[index];              \
  106.     else if ( (posbytes) == POS_2_BYTES )           \
  107.       pos = (occur)->p.pos2[index];                 \
  108.     else                                            \
  109.       pos = (occur)->p.pos4[index];                 \
  110.   }
  111.  
  112. #define SET_POS(pos,occur,index,posbytes)       \
  113.   {                                             \
  114.     if ( (posbytes) == POS_3_BYTES )            \
  115.     {                                           \
  116.       (occur)->p.pos3.hi[index] = (pos) >> 16;  \
  117.       (occur)->p.pos3.lo[index] = (pos);        \
  118.     }                                           \
  119.     else if ( (posbytes) == POS_2_BYTES )       \
  120.       (occur)->p.pos2[index] = pos;             \
  121.     else                                        \
  122.       (occur)->p.pos4[index] = pos;             \
  123.   }
  124.  
  125. /* ------------------------------------------------------ */
  126. /*                       Prototypes                       */
  127.  
  128. void InitFind (
  129.   char *textToSearch,
  130.   long textLength,
  131.   void *privateStorage,
  132.   long storageSize
  133. );
  134.  
  135. long FindWordOccurrence (
  136.   char *wordToFind,
  137.   long wordLength,
  138.   long occurrenceToFind,
  139.   char *textToSearch,
  140.   long textLength,
  141.   void *privateStorage,
  142.   long storageSize
  143. );
  144.  
  145. static long InitFindBody (
  146.   uchar   *textToSearch,
  147.   long    textLength,
  148.   Private *private,
  149.   uchar   *endPrivateStorage
  150. );
  151.  
  152. static Word *LookupWord (
  153.   Private *private,
  154.   char    *textToSearch,
  155.   char    *wordText,
  156.   long    wordLength,
  157.   ulong   hash
  158. );
  159.  
  160. static char PickNullChar (
  161.   Private *private,
  162.   uchar   *textStart,     /* start of unparsed text */
  163.   uchar   *textEnd        /* end of all text        */
  164. );
  165.  
  166. static char *BMH_Search(
  167.   ulong *hashCodes,       /* private->hashCodes      */
  168.   char  *wordToFind,
  169.   long  wordLength,
  170.   long  occurrenceToFind, /* 0 is 1st occurrence     */
  171.   char  *textStart,       /* start of unparsed text  */
  172.   char  *textEnd,         /* end of all text         */
  173.   char  nullChar          /* private->nullChar       */
  174. );
  175.  
  176. static char *SimpleSearch(
  177.   ulong *hashCodes,       /* private->hashCodes      */
  178.   char  *wordToFind,
  179.   long  wordLength,       /* 1..3                    */
  180.   long  occurrenceToFind, /* 0 is 1st occurrence     */
  181.   char  *textStart,       /* start of unparsed text  */
  182.   char  *textEnd          /* end of all text         */
  183. );
  184.  
  185. /* ------------------------------------------------------ */
  186. /*                        InitFind                        */
  187.  
  188. void InitFind (
  189.   char *textToSearch,
  190.   long textLength,
  191.   void *privateStorage,
  192.   long storageSize
  193. )
  194. {
  195.   Private *private = privateStorage;
  196.  
  197.   private->endParsedText =
  198.     InitFindBody(
  199.         (uchar *)textToSearch,
  200.         textLength,
  201.         privateStorage,
  202.         (uchar *)privateStorage + storageSize
  203.     );
  204.  
  205.   if ( private->endParsedText != -1 )
  206.     private->nullChar =
  207.       PickNullChar(
  208.             private,
  209.             (uchar *)textToSearch + private->endParsedText,
  210.             (uchar *)textToSearch + textLength );
  211.   else
  212.     private->nullChar = NO_NULL_CHAR;
  213. }
  214.  
  215. /* ------------------------------------------------------ */
  216. /*                        InitFindBody                    */
  217.  
  218. /*
  219.   This function does most of the work for InitFind().
  220.   The arguments have been recast into a more useful form;
  221.   uchar and ulong are used a lot so that we don't have to
  222.   worry about the sign, especially when indexing
  223.   private->hashCodes[].
  224.  
  225.   The return value is the character position when the
  226.   unparsed text begins (if we run out of private storage),
  227.   or -1 if all the text was parsed.
  228. */
  229.  
  230. static long InitFindBody (
  231.   uchar   *textToSearch,
  232.   long    textLength,
  233.   Private *private,
  234.   uchar   *endPrivateStorage
  235. )
  236. {
  237.   uchar       *alloc, *textPos, *textEnd, *wordStart;
  238.   long        wordLength;
  239.   ulong       hash, code;
  240.   Word        *word;
  241.   Occurrence  *occur;
  242.  
  243.   /*
  244.     Init table of hash codes. The remaining entries are
  245.     guaranteed to be initialized to zero. The hash codes
  246.     were chosen so that any two codes differ by at least
  247.     five bits.
  248.   */
  249.  
  250.   {
  251.     ulong *table = private->hashCodes;  /* reduces typing */
  252.  
  253.     table['0'] = 0xFFC0;  table['5'] = 0xF492;
  254.     table['1'] = 0xFE07;  table['6'] = 0xF31E;
  255.     table['2'] = 0xF98B;  table['7'] = 0xF2D9;
  256.     table['3'] = 0xF84C;  table['8'] = 0xCF96;
  257.     table['4'] = 0xF555;  table['9'] = 0xCE51;
  258.  
  259.     table['A'] = 0xC9DD;  table['N'] = 0xA245;
  260.     table['B'] = 0xC81A;  table['O'] = 0x9F0A;
  261.     table['C'] = 0xC503;  table['P'] = 0x9ECD;
  262.     table['D'] = 0xC4C4;  table['Q'] = 0x9941;
  263.     table['E'] = 0xC348;  table['R'] = 0x9886;
  264.     table['F'] = 0xC28F;  table['S'] = 0x959F;
  265.     table['G'] = 0xAF5C;  table['T'] = 0x9458;
  266.     table['H'] = 0xAE9B;  table['U'] = 0x93D4;
  267.     table['I'] = 0xA917;  table['V'] = 0x9213;
  268.     table['J'] = 0xA8D0;  table['W'] = 0x6DD3;
  269.     table['K'] = 0xA5C9;  table['X'] = 0x6C14;
  270.     table['L'] = 0xA40E;  table['Y'] = 0x6B98;
  271.     table['M'] = 0xA382;  table['Z'] = 0x6A5F;
  272.  
  273.     table['a'] = 0x6746;  table['n'] = 0x3C88;
  274.     table['b'] = 0x6681;  table['o'] = 0x3B04;
  275.     table['c'] = 0x610D;  table['p'] = 0x3AC3;
  276.     table['d'] = 0x60CA;  table['q'] = 0x37DA;
  277.     table['e'] = 0x5D85;  table['r'] = 0x361D;
  278.     table['f'] = 0x5C42;  table['s'] = 0x3191;
  279.     table['g'] = 0x5BCE;  table['t'] = 0x3056;
  280.     table['h'] = 0x5A09;  table['u'] = 0x0D19;
  281.     table['i'] = 0x5710;  table['v'] = 0x0CDE;
  282.     table['j'] = 0x56D7;  table['w'] = 0x0B52;
  283.     table['k'] = 0x515B;  table['x'] = 0x0A95;
  284.     table['l'] = 0x509C;  table['y'] = 0x078C;
  285.     table['m'] = 0x3D4F;  table['z'] = 0x064B;
  286.   }
  287.  
  288.   /*
  289.     Determine the number of bytes needed to store
  290.     each occurrence position.
  291.   */
  292.  
  293.   if ( textLength <= 0x10000L )
  294.     private->posBytes = POS_2_BYTES;
  295.   else if ( textLength <= 0x1000000L )
  296.     private->posBytes = POS_3_BYTES;
  297.   else
  298.     private->posBytes = POS_4_BYTES;
  299.  
  300.   /*
  301.     Set up variables to handle allocation of
  302.     private storage.
  303.   */
  304.  
  305.   alloc = (uchar *)&private->heap;
  306.  
  307.   /* Parse the text */
  308.  
  309.   textPos = textToSearch;
  310.   textEnd = textPos + textLength;
  311.  
  312.   while ( textPos != textEnd )
  313.   {
  314.     /* Search for start of word */
  315.     while ( private->hashCodes[*textPos] == 0 )
  316.     {
  317.       textPos++;
  318.       if ( textPos == textEnd )
  319.         return -1;  /* parse all text */
  320.     }
  321.     wordStart = textPos;
  322.  
  323.     /* Search for end of word; generate hash value too */
  324.     hash = 0;
  325.     while ( textPos != textEnd &&
  326.             (code = private->hashCodes[ *textPos ]) != 0 )
  327.     {
  328.       hash = (hash << 1) ^ code;
  329.       textPos++;
  330.     }
  331.     wordLength = textPos - wordStart;
  332.     hash = (hash & 0xFFFFFF) | (wordLength << 24);
  333.  
  334.     /*
  335.       Record the occurrence. First we see if a Word struct
  336.       exists for this word and whether we need to allocate
  337.       a new Occurrence struct.
  338.     */
  339.  
  340.     word = LookupWord(
  341.                 private,
  342.                 (char *)textToSearch,
  343.                 (char *)wordStart,
  344.                 wordLength,
  345.                 hash );
  346.     if ( word )
  347.     {
  348.       long allocateNewBlock, blockSize, i, pos;
  349.  
  350.       /*
  351.         This word has occurred before, so it already has
  352.         a Word struct. See if there's room in the last
  353.         Occurrence block for another entry. Remember that
  354.         entry #0 in the Occurrence block is always in use,
  355.         so we can start checking at entry #1 for a non-zero
  356.         entry.
  357.       */
  358.  
  359.       occur = word->last;
  360.       allocateNewBlock = TRUE;
  361.       switch ( private->posBytes )
  362.       {
  363.         case POS_2_BYTES:  blockSize = 6; break;
  364.         case POS_3_BYTES:  blockSize = 4; break;
  365.         case POS_4_BYTES:  blockSize = 3; break;
  366.       }
  367.  
  368.       for ( i = 1; i < blockSize; i++ )
  369.       {
  370.         GET_POS( pos, occur, i, private->posBytes )
  371.         if ( pos == 0 )
  372.         {
  373.           SET_POS( wordStart - textToSearch, occur, i,
  374.                    private->posBytes )
  375.           allocateNewBlock = FALSE;
  376.           break;
  377.         }
  378.       }
  379.  
  380.       if ( allocateNewBlock )
  381.       {
  382.         /* Block is full. Allocate new Occurrence block */
  383.         occur = (Occurrence *) alloc;
  384.         alloc += ALLOC_SIZE( sizeof(Occurrence) );
  385.         if ( alloc >= endPrivateStorage )
  386.           return wordStart-textToSearch; /* out of memory */
  387.  
  388.         /*
  389.           Init the new struct and link it to the end
  390.           of the occurence list.
  391.         */
  392.         SET_POS( wordStart - textToSearch, occur, 0,
  393.                  private->posBytes )
  394.         word->last->next = occur;
  395.         word->last = occur;
  396.       }
  397.     }
  398.     else
  399.     {
  400.       long i;
  401.  
  402.       /*
  403.         This is a new word. Allocate a new Word struct,
  404.         which contains an Occurrence struct too.
  405.       */
  406.       word = (Word *) alloc;
  407.       alloc += ALLOC_SIZE( sizeof(Word) );
  408.       if ( alloc >= endPrivateStorage )
  409.         return wordStart-textToSearch ;  /* out of memory */
  410.  
  411.       /*
  412.         Link it to the start of the Word list, coming off
  413.         the hash table.
  414.       */
  415.       word->next = private->hashTable[ hash & HASH_MASK ];
  416.       private->hashTable[ hash & HASH_MASK ] = word;
  417.  
  418.       /* Init the Word struct */
  419.       word->hash = hash;
  420.       word->last = &word->first;
  421.  
  422.       /* Init the Occurrence struct */
  423.       SET_POS( wordStart - textToSearch, &word->first, 0,
  424.                private->posBytes )
  425.     }
  426.   }
  427.  
  428.   /* Finished parsing text */
  429.   return -1;
  430. }
  431.  
  432. /* ------------------------------------------------------ */
  433. /*                  FindWordOccurrence                    */
  434.  
  435. long FindWordOccurrence (
  436.   char *wordToFind,
  437.   long wordLength,
  438.   long occurrenceToFind,
  439.   char *textToSearch,
  440.   long textLength,
  441.   void *privateStorage,
  442.   long storageSize
  443. )
  444. {
  445.   Private *private = privateStorage;
  446.   Word  *word;
  447.   ulong hash;
  448.  
  449.   /* Make occurenceToFind zero-based */
  450.   occurrenceToFind--;
  451.  
  452.   /* Generate hash value for word to find */
  453.   hash = 0;
  454.   {
  455.     long remain = wordLength;
  456.     uchar *p = (uchar *) wordToFind;
  457.     while ( remain > 0 )
  458.     {
  459.       hash = (hash << 1) ^ private->hashCodes[*p++];
  460.       remain--;
  461.     }
  462.     hash = (hash & 0xFFFFFF) | (wordLength << 24);
  463.   }
  464.  
  465.   /* Look for word/occurrence in hash table */
  466.   word = LookupWord( private, textToSearch, wordToFind,
  467.                      wordLength, hash );
  468.   if ( word )
  469.   {
  470.     Occurrence *occur = &word->first;
  471.     long blockSize, pos, i;
  472.  
  473.     /*
  474.       Word exists in hash table, so go down the
  475.       occurrence list.
  476.     */
  477.  
  478.     switch ( private->posBytes )
  479.     {
  480.       case POS_2_BYTES: blockSize = 6;  break;
  481.       case POS_3_BYTES: blockSize = 4;  break;
  482.       case POS_4_BYTES: blockSize = 3;  break;
  483.     }
  484.  
  485.     while ( occur && occurrenceToFind >= blockSize )
  486.     {
  487.       occurrenceToFind -= blockSize;
  488.       occur = occur->next;
  489.     }
  490.  
  491.     if ( occur )
  492.     {
  493.       GET_POS( pos, occur, occurrenceToFind,
  494.                private->posBytes )
  495.       if ( occurrenceToFind == 0 || pos != 0 )
  496.         return pos;
  497.       occurrenceToFind -= blockSize;
  498.     }
  499.  
  500.     occur = word->last;
  501.     for ( i = 0; i < blockSize; i++ )
  502.     {
  503.       GET_POS( pos, occur, i, private->posBytes )
  504.       if ( pos == 0 )
  505.         occurrenceToFind++;
  506.     }
  507.   }
  508.  
  509.   /* Not in parsed text, so check the unparsed text */
  510.   if ( private->endParsedText != -1 )
  511.   {
  512.     char *p;
  513.     if ( wordLength > 3 )
  514.       p = BMH_Search(
  515.               private->hashCodes,
  516.               wordToFind,
  517.               wordLength,
  518.               occurrenceToFind,
  519.               textToSearch + private->endParsedText,
  520.               textToSearch + textLength,
  521.               private->nullChar );
  522.     else
  523.       p = SimpleSearch(
  524.               private->hashCodes,
  525.               wordToFind,
  526.               wordLength,
  527.               occurrenceToFind,
  528.               textToSearch + private->endParsedText,
  529.               textToSearch + textLength );
  530.     if (p)
  531.       return (p - textToSearch);
  532.   }
  533.  
  534.   /* Not found */
  535.   return -1;
  536. }
  537.  
  538. /* ------------------------------------------------------ */
  539. /*                        LookupWord                      */
  540.  
  541. /* Look up a word in the hash table */
  542.  
  543. static Word *LookupWord (
  544.   Private *private,
  545.   char    *textToSearch,
  546.   char    *wordText,
  547.   long    wordLength,
  548.   ulong   hash
  549. )
  550. {
  551.   Word *word = private->hashTable[ hash & HASH_MASK ];
  552.   while ( word )
  553.   {
  554.     if ( word->hash == hash )
  555.     {
  556.       char *w1, *w2;
  557.       long pos, remain = wordLength;
  558.  
  559.       /*
  560.         The hash values match, so compare characters to make
  561.         sure it's the right word. We already know the word
  562.         length is correct since the length is contained
  563.         in the upper eight bits of the hash value.
  564.       */
  565.       GET_POS( pos, &word->first, 0, private->posBytes )
  566.       w1 = textToSearch + pos;
  567.       w2 = wordText;
  568.       while ( remain-- > 0 && *w1++ == *w2++ )
  569.         ;
  570.       if ( remain == -1 )
  571.         return word;
  572.     }
  573.     word = word->next;
  574.   }
  575.   return NULL;
  576. }
  577.  
  578. /* ------------------------------------------------------ */
  579. /*                        PickNullChar                    */
  580.  
  581. /*
  582.   Find a character that doesn't appear anywhere in
  583.   the unparsed text. BMH_Search() is faster if such
  584.   a character can be found.
  585. */
  586.  
  587. static char PickNullChar (
  588.   Private *private,
  589.   uchar   *textStart,
  590.   uchar   *textEnd
  591. )
  592. {
  593.   long i;
  594.   uchar *p, occurs[ ALPHABET_SIZE ];
  595.  
  596.   for ( i = 0; i < ALPHABET_SIZE; i++ )
  597.     occurs[i] = FALSE;
  598.  
  599.   for ( p = textStart; p < textEnd; p++ )
  600.     occurs[*p] = TRUE;
  601.  
  602.   for ( i = 0; i < ALPHABET_SIZE; i++ )
  603.     if ( occurs[i] == FALSE && private->hashCodes[i] == 0 )
  604.       return i;
  605.  
  606.   return NO_NULL_CHAR;
  607. }
  608.  
  609. /* ------------------------------------------------------ */
  610. /*                        BMH_Search                      */
  611.  
  612. /*
  613.   Search the unparsed text using the Boyer-Moore-Horspool
  614.   algorithm. Ideally a null character is supplied (one that
  615.   appears in neither the search string nor the text being
  616.   searched). This allows the inner loop to be faster.
  617. */
  618.  
  619. static char *BMH_Search (
  620.   ulong *hashCodes,       /* private->hashCodes     */
  621.   char  *wordToFind,
  622.   long  wordLength,
  623.   long  occurrenceToFind, /* 0 is first occurrence  */
  624.   char  *textStart,       /* start of unparsed text */
  625.   char  *textEnd,         /* end of unparsed text   */
  626.   char  nullChar          /* private->nullChar      */
  627. )
  628. {
  629.   long  i;
  630.   char  *text, *wordEnd;
  631.   char  word[256];
  632.   long  offset[ ALPHABET_SIZE ];
  633.  
  634.   /*
  635.     Copy the search string to a private buffer, where
  636.     the first character is the null character.
  637.   */
  638.  
  639.   word[0] = nullChar;
  640.   for ( i = 0; i < wordLength; i++ )
  641.     word[i+1] = wordToFind[i];
  642.  
  643.   /* Set up the offset[] lookup table */
  644.  
  645.   for ( i = 0; i < ALPHABET_SIZE; i++ )
  646.     offset[i] = wordLength;
  647.  
  648.   for ( i = 1; i < wordLength; i++ )
  649.     offset[ word[i] ] = wordLength - i;
  650.  
  651.   /* Let the search begin... */
  652.  
  653.   wordEnd = word + wordLength;
  654.   text = textStart + wordLength - 1;
  655.  
  656.   if ( nullChar == NO_NULL_CHAR )
  657.   {
  658.     /* No null character, so use a slower inner loop */
  659.     while ( text < textEnd )
  660.     {
  661.       long i;
  662.       char *p, *q;
  663.       for ( i = wordLength, p = wordEnd, q = text;
  664.             i > 0 && *p == *q;
  665.             i--, p--, q-- )
  666.         ;
  667.  
  668.       /*
  669.         If i == 0, we have found the search string.
  670.         Now we make sure that it is delimited.
  671.       */
  672.       if ( i == 0 && hashCodes[*q] == 0 &&
  673.            (text+1 == textEnd || hashCodes[text[1]] == 0) )
  674.       {
  675.         if ( occurrenceToFind == 0 )
  676.           return q+1;
  677.         occurrenceToFind--;
  678.       }
  679.  
  680.       text += offset[*text];
  681.     }
  682.   }
  683.   else
  684.   {
  685.     /*
  686.       There is a null character (usual case), so
  687.       we can use a faster and simpler inner loop.
  688.     */
  689.     while ( text < textEnd )
  690.     {
  691.       char *p, *q;
  692.       for ( p = wordEnd, q = text; *p == *q; p--, q-- )
  693.         ;
  694.       if ( p == word && hashCodes[*q] == 0 &&
  695.            (text+1 == textEnd || hashCodes[text[1]] == 0) )
  696.       {
  697.         if ( occurrenceToFind == 0 )
  698.           return q+1;
  699.         occurrenceToFind--;
  700.       }
  701.       text += offset[*text];
  702.     }
  703.   }
  704.   return NULL;
  705. }
  706.  
  707. /* ------------------------------------------------------ */
  708. /*                    SimpleSearch                        */
  709.  
  710. /*
  711.   Search the unparsed text using a simple search algorithm.
  712.   Note that wordLength must be 1, 2, or 3. This algorithm
  713.   runs faster than BMH_Search() for small search strings.
  714. */
  715.  
  716. static char *SimpleSearch(
  717.   ulong *hashCodes,       /* private->hashCodes      */
  718.   char  *wordToFind,
  719.   long  wordLength,       /* 1..3                    */
  720.   long  occurrenceToFind, /* 0 is 1st occurrence     */
  721.   char  *textStart,       /* start of unparsed text  */
  722.   char  *textEnd          /* end of all text         */
  723. )
  724. {
  725.   char *text, first;
  726.  
  727.   first = wordToFind[0];
  728.   text = textStart;
  729.  
  730.   if ( wordLength == 1 )
  731.   {
  732.     while ( text < textEnd )
  733.     {
  734.       while ( text < textEnd && *text != first )
  735.         text++;
  736.       if ( hashCodes[*(text-1)] == 0 &&
  737.            hashCodes[text[wordLength]] == 0 )
  738.       {
  739.         if ( occurrenceToFind == 0 )
  740.           return text;
  741.         occurrenceToFind--;
  742.       }
  743.     text++;
  744.     }
  745.   }
  746.   else if ( wordLength == 2 )
  747.   {
  748.     while ( text < textEnd )
  749.     {
  750.       while ( text < textEnd && *text != first )
  751.         text++;
  752.       if ( text[1] == wordToFind[1] &&
  753.            hashCodes[*(text-1)] == 0 &&
  754.            hashCodes[text[wordLength]] == 0 )
  755.       {
  756.         if ( occurrenceToFind == 0 )
  757.           return text;
  758.         occurrenceToFind--;
  759.       }
  760.     text++;
  761.     }
  762.   }
  763.   else /* wordLength == 3 */
  764.   {
  765.     while ( text < textEnd )
  766.     {
  767.       while ( text < textEnd && *text != first )
  768.         text++;
  769.       if ( text[1] == wordToFind[1] &&
  770.            text[2] == wordToFind[2] &&
  771.            hashCodes[*(text-1)] == 0 &&
  772.            hashCodes[text[wordLength]] == 0 )
  773.       {
  774.         if ( occurrenceToFind == 0 )
  775.           return text;
  776.         occurrenceToFind--;
  777.       }
  778.     text++;
  779.     }
  780.   }
  781.   return NULL;
  782. }
  783.  
  784.  
  785.  
  786.